package com.fayou.algorithm.sort;

import com.fayou.algorithm.queue.AxinBlockQueue1;

import javax.swing.tree.TreeNode;
import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] a = {1, 1, 1, 2, 3, 4, 5, 6, 9, 9, 12, 53};

//        qkSort(a, 0, a.length - 1);


        AxinBlockQueue1 queue1 = new AxinBlockQueue1(100);

        queue1.qkSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }


    private static void qkSort(int[] a, int start, int end) {
        if (a == null || a.length == 0) {
            return;
        }

        if (start > end) {
            return;
        }


        int left = start;
        int right = end;

        int temp = a[start];

        while (left < right) {
            while (left < right && a[right] > temp) {
                right--;
            }

            a[left] = a[right];


            while (left < right && a[left] <= temp) {
                left++;
            }

            a[right] = a[left];

        }

        a[left] = temp;
        qkSort(a, start, left - 1);
        qkSort(a, left + 1, end);


    }

//    private static void qkSort(int[] a, int start, int end) {
//        if (a == null || a.length == 0) {
//            return;
//        }
//
//        if (start > end) {
//            return;
//        }
//
//        int left = start;
//        int right = end;
//        int temp = a[left];
//
//        while (left < right) {
//            while (left < right && a[right] > temp) {
//                right--;
//            }
//            a[left] = a[right];
//
//            while (left < right && a[left] <= temp) {
//                left++;
//            }
//            a[right] = a[left];
//        }
//        a[left] = temp;
//
//        qkSort(a, start, left - 1);
//        qkSort(a, left + 1, end);
//    }
}
